Fibonacci Words
Memory limit: 64 MB
The sequence of Fibonacci words is defined as follows:
,
,
.
is the concatenation of
and
.
The first few Fibonacci words are:
b,a,ab,aba,abaab,abaababa,abaababaabaab,...
A word
is a subword of a word
if
can be written as
for some (possibly empty) words
and
.
Task
Write a program which:
-
reads a word
(a sequence of letters a and b)
and a sequence number
of the Fibonacci word
;
-
computes the number of times the word
occurs in
as a subword
and the number of nonempty words that occur as a subword in
at least as frequently as
.
-
writes the answer to the standard output.
Input
The first line contains one integer
(
). We will examine the Fibonacci word
.
The second line contains one word
(a sequence of no more than
and no less than one letter a and/or b).
Output
In the first and only line your program should write two numbers separated by a single
space. The former is the number of times the word
occurs in
as a subword.
The latter is the number of nonempty words which occur in
as subwords at least as frequently as
occurs in
.
Both numbers should be written modulo
(you should write the remainder of the division of these numbers by
).
You can assume, that the word
is a subword of
the given Fibonacci word.
Example
For the input data:
5
aba
the correct result is:
3 5
The subwords of
which occur in
at least as frequently as aba are: a, b, ab, ba and aba.
Task author: Jakub Radoszewski.